package p300;

import java.util.Arrays;

/**
 * @author pengjz <br>
 * @version 1.0 <br>
 * @description Leetcode_300 <br>
 * @date 2021/3/5 22:23 <br>
 */
public class Leetcode_300 {

    public int lengthOfLIS(int[] nums) {
        int[] res = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int idx = Arrays.binarySearch(res, 0, len, num);
            idx = idx < 0 ? -idx - 1 : idx;
            res[idx] = num;
            if (idx == len) {
                len++;
            }
        }
        return len;
    }

    public static void main(String[] args) {
        Leetcode_300 leetcode_300 = new Leetcode_300();
        System.out.println(leetcode_300.lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
    }

}
